package code;

//最后一块石头的重量II:https://leetcode.cn/problems/last-stone-weight-ii/
public class lastStoneWeight {
	public int lastStoneWeightII(int[] stones) {
        int sum=0;
        for(int x:stones) sum+=x;
        int target=sum/2,n=stones.length;
        int[][] dp=new int[n+1][target+1];
        //dp[i][j]: 从i-1个元素中选，获得的最大容量
        
        //状态转移方程
        //1.不选：dp[i-1][j]
        //2.选：dp[i-1][j-stons[i-1]]+stons[i-1]
        
        //初始化
        //1.i=0&&j!=0时，0
        //2.i!=0&&j=0时，0

        for(int i=1;i<=n;i++){
            for(int j=1;j<=target;j++){
                dp[i][j]=dp[i-1][j];
                if(j-stones[i-1]>=0){
                    dp[i][j]=Math.max(dp[i][j],dp[i-1][j-stones[i-1]]+stones[i-1]);
                }
            }
        }
        return sum-2*dp[n][target];
    }
}
